package org.example;

/**
 * 随机链表的复制
 */
public class Solution32 {

    public RandomNode copyRandomList(RandomNode head) {
        if (head == null) {
            return null;
        }

        RandomNode current = head;

        // 1. 遍历链表，创建newNode节点，插入到current和current.next之间
        while (current != null) {
            RandomNode newNode = new RandomNode(current.val);
            newNode.next = current.next;
            current.next = newNode;
            current = newNode.next;
        }

        // 2. 再次遍历链表，设置每个新节点的随机指针
        current = head;
        while (current != null) {
            if (current.random != null) {
                current.next.random = current.random.next;
            }
            current = current.next.next;
        }

        // 3. 拆分链表
        current = head;
        RandomNode newHead = head.next;
        RandomNode newCurrent = newHead;
        while (current != null) {
            current.next = newCurrent.next;
            current = current.next;
            if (newCurrent.next != null) {
                newCurrent.next = newCurrent.next.next;
                newCurrent = newCurrent.next;
            }
        }

        return newHead;
    }

}
